package cn.shutdown.leetcode;//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
//
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 
//
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
//
// 示例： 
//
// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 0 -> 8
//原因：342 + 465 = 807
// 
// Related Topics 链表 数学 
// 👍 4566 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

public class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //获取node节点值，从个位向高位顺序
        List<Integer> node1ValueList = getAllListNode(l1);
        List<Integer> node2ValueList = getAllListNode(l2);
        List<Integer> resultList = new ArrayList<Integer>();
        List<Integer> biggerCountList = node1ValueList.size() >= node2ValueList.size() ? node1ValueList : node2ValueList;
        List<Integer> smallerCountList = node2ValueList.size() <= node1ValueList.size() ? node2ValueList : node1ValueList;
        System.out.println(biggerCountList);
        System.out.println(smallerCountList);
        Integer increase = 0;
        for (int i = 0; i < biggerCountList.size(); i++) {
            int num = (biggerCountList.get(i) + ((smallerCountList.size() > i) ? smallerCountList.get(i) : 0)) + increase;
            int result = num % 10;
            //计算进位数
            increase = num / 10;
            System.out.println(num + " " + increase);
            resultList.add(result);
        }
        if (increase > 0) {
            //说明仍有进位
            resultList.add(increase);
        }
        return buildListNode(resultList);
    }

    private ListNode buildListNode(List<Integer> resultList) {
        System.out.println(resultList);

        List<ListNode> finalList = new ArrayList<ListNode>();
        boolean beforeIsZero = false;
        for (int i = resultList.size() - 1; i >= 0; i--) {
            if (i == resultList.size() && resultList.get(i) == 0) {
                beforeIsZero = true;
                continue;
            }
            //判断前位是否是0
            if (beforeIsZero) {
                if (resultList.get(i) == 0) {
                    continue;
                } else {
                    beforeIsZero = false;
                    finalList.add(new ListNode(resultList.get(i)));
                }
            } else {
                finalList.add(new ListNode(resultList.get(i)));
            }
        }
        if (finalList.size() == 0) {
            return new ListNode(0);
        } else {
            for (int i = finalList.size() - 1; i >= 0; i--) {
                ListNode finalNode = finalList.get(i);
                System.out.println(finalNode);
                if (i > 0) {
                    finalNode.next = finalList.get(i - 1);
                    finalNode = finalList.get(i);
                }
            }
            return finalList.get(finalList.size() - 1);
        }
    }

    private List<Integer> getAllListNode(ListNode listNode) {
        boolean hasNext = true;
        List<Integer> nodeValList = new ArrayList();
        ListNode tempListNode = listNode;
        while (hasNext) {
            if (tempListNode == null) {
                return nodeValList;
            }
            nodeValList.add(tempListNode.val);
            tempListNode = tempListNode.next;
            if (tempListNode == null) {
                hasNext = false;
            }
        }
        return nodeValList;
    }

    public static void main(String[] args) {

//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(8);
//        l1.next = l2;
//
//
//        ListNode l4 = new ListNode(0);


        ListNode l1 = new ListNode(5);
        ListNode l4 = new ListNode(5);

        System.out.println(l1.toString());
        System.out.println(l4.toString());

        ListNode listNode = new Solution().addTwoNumbers(l1, l4);
        System.out.println(listNode.toString());

    }
}
//leetcode submit region end(Prohibit modification and deletion)
